#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void
print_array(long long int int_array[], unsigned long long int array_length)
{
    printf("[");
    for (unsigned long long int n=0; n < array_length-1; n+=1) {
	printf("%lld, ", int_array[n]);
    }
    if (array_length)
	printf("%lld", int_array[array_length-1]);

    printf("]\n");
}


void
max_heapify(long long int heap[], unsigned long long int x,
	    unsigned long long int length)
{
    unsigned long long int left_child = x * 2 + 1;
    unsigned long long int right_child = left_child + 1;
    unsigned long long int largest = x;

    if ((left_child <= (length - 1)) && (heap[left_child] > heap[x]))
	largest = left_child;
    if ((right_child <= (length - 1)) && (heap[right_child] > heap[largest]))
	largest = right_child;

    if (largest != x) {
	int temp = heap[x];

	heap[x] = heap[largest];
	heap[largest] = temp;

	max_heapify(heap, largest, length);
    }
}


void
build_heap(long long int heap[], unsigned long long int length)
{
    for (long long int x = length / 2; x >= 0; x -= 1) {
	max_heapify(heap, x, length);
    }
}


// Name has a trailing underscore as stdlib.h has a function named heapsort().
void
heapsort_(long long int heap[], unsigned long long int length)
{
    build_heap(heap, length);

    for (unsigned long long int x = length - 1; x > 0; x -= 1) {
	long long int temp = heap[0];

	heap[0] = heap[x];
	heap[x] = temp;

	max_heapify(heap, 0, x);
    }
}


int
main(int argc, char *argv[])
{
    unsigned long long int length = argc - 1;
    long long int heap[length];

    for (unsigned long long int x = 0; x < length; x += 1)
	heap[x] = atoi(argv[x+1]);

    heapsort_(heap, length);

    print_array(heap, length);

    return 0;
}
